home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / msdos / raytrace / pov / source / csg.c < prev    next >
C/C++ Source or Header  |  1993-10-28  |  10KB  |  392 lines
  1. /****************************************************************************
  2. *                   csg.c
  3. *
  4. *  This module implements routines for constructive solid geometry.
  5. *
  6. *  from Persistence of Vision Raytracer
  7. *  Copyright 1993 Persistence of Vision Team
  8. *---------------------------------------------------------------------------
  9. *  NOTICE: This source code file is provided so that users may experiment
  10. *  with enhancements to POV-Ray and to port the software to platforms other 
  11. *  than those supported by the POV-Ray Team.  There are strict rules under
  12. *  which you are permitted to use this file.  The rules are in the file
  13. *  named POVLEGAL.DOC which should be distributed with this file. If 
  14. *  POVLEGAL.DOC is not available or for more info please contact the POV-Ray
  15. *  Team Coordinator by leaving a message in CompuServe's Graphics Developer's
  16. *  Forum.  The latest version of POV-Ray may be found there as well.
  17. *
  18. * This program is based on the popular DKB raytracer version 2.12.
  19. * DKBTrace was originally written by David K. Buck.
  20. * DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
  21. *
  22. *****************************************************************************/
  23.  
  24. #include "frame.h"
  25. #include "vector.h"
  26. #include "povproto.h"
  27.  
  28. METHODS CSG_Union_Methods =
  29.   { 
  30.   All_CSG_Union_Intersections,
  31.   Inside_CSG_Union, NULL /*Normal*/,
  32.   Copy_CSG,
  33.   Translate_CSG, Rotate_CSG,
  34.   Scale_CSG, Transform_CSG, Invert_CSG_Union, Destroy_CSG
  35. };
  36.  
  37. METHODS CSG_Merge_Methods =
  38.   { 
  39.   All_CSG_Merge_Intersections,
  40.   Inside_CSG_Union, NULL /*Normal*/,
  41.   Copy_CSG,
  42.   Translate_CSG, Rotate_CSG,
  43.   Scale_CSG, Transform_CSG, Invert_CSG_Union, Destroy_CSG
  44. };
  45.  
  46. METHODS CSG_Intersection_Methods =
  47.   { 
  48.   All_CSG_Intersect_Intersections,
  49.   Inside_CSG_Intersection, NULL /*Normal*/,
  50.   Copy_CSG,
  51.   Translate_CSG, Rotate_CSG,
  52.   Scale_CSG, Transform_CSG, Invert_CSG_Intersection, Destroy_CSG
  53. };
  54.  
  55. int All_CSG_Union_Intersections (Object, Ray, Depth_Stack)
  56. OBJECT *Object;
  57. RAY *Ray;
  58. ISTACK *Depth_Stack;
  59.   {
  60.   register int Found;
  61.   OBJECT *Current_Sib, *Clip;
  62.   ISTACK *Local_Stack;
  63.   INTERSECTION *Sibling_Intersection;
  64.  
  65.   Found = FALSE;
  66.  
  67.   if ((Clip = Object->Clip) == NULL) /* Use shortcut if no clip */
  68.     {
  69.     for (Current_Sib = ((CSG *)Object)->Children;
  70.          Current_Sib != NULL ;
  71.          Current_Sib = Current_Sib->Sibling)
  72.       if (Ray_In_Bounds (Ray, Current_Sib->Bound))
  73.         if (All_Intersections (Current_Sib, Ray, Depth_Stack))
  74.           Found = TRUE;
  75.     }
  76.   else
  77.     {
  78.     Local_Stack = open_istack ();
  79.  
  80.     for (Current_Sib = ((CSG *)Object)->Children;
  81.          Current_Sib != NULL ;
  82.          Current_Sib = Current_Sib->Sibling)
  83.       if (Ray_In_Bounds (Ray, Current_Sib->Bound))
  84.         if (All_Intersections (Current_Sib, Ray, Local_Stack))
  85.           while ((Sibling_Intersection = pop_entry(Local_Stack)) != NULL)
  86.             if (Point_In_Clip (&Sibling_Intersection->IPoint, Clip))
  87.               {
  88.               push_copy (Depth_Stack, Sibling_Intersection);
  89.               Found = TRUE;
  90.               }
  91.     close_istack (Local_Stack);
  92.     }
  93.   return (Found);
  94.   }
  95.  
  96. int All_CSG_Intersect_Intersections (Object, Ray, Depth_Stack)
  97. OBJECT *Object;
  98. RAY *Ray;
  99. ISTACK *Depth_Stack;
  100.   {
  101.   int Maybe_Found, Found;
  102.   OBJECT *Current_Sib, *Inside_Sib;
  103.   ISTACK *Local_Stack;
  104.   INTERSECTION *Sibling_Intersection;
  105.  
  106.   Local_Stack = open_istack ();
  107.  
  108.   Found = FALSE;
  109.  
  110.   for (Current_Sib = ((CSG *)Object)->Children;
  111.   Current_Sib != NULL;
  112.   Current_Sib = Current_Sib->Sibling) 
  113.     {
  114.     if (Ray_In_Bounds (Ray, Current_Sib->Bound))
  115.       if (All_Intersections (Current_Sib, Ray, Local_Stack))
  116.         while ((Sibling_Intersection = pop_entry(Local_Stack)) != NULL)
  117.           {
  118.           Maybe_Found = TRUE;
  119.           for (Inside_Sib = ((CSG *)Object)->Children;
  120.           Inside_Sib != NULL;
  121.           Inside_Sib = Inside_Sib->Sibling)
  122.             if (Inside_Sib != Current_Sib)
  123.               if (!Inside_Object (&Sibling_Intersection->IPoint, Inside_Sib)) 
  124.                 {
  125.                 Maybe_Found = FALSE;
  126.                 break;
  127.                 }
  128.           if (Maybe_Found)
  129.             if (Point_In_Clip (&Sibling_Intersection->IPoint, Object->Clip))
  130.               {
  131.               push_copy(Depth_Stack, Sibling_Intersection);
  132.               Found = TRUE;
  133.               }
  134.           }
  135.     }
  136.   close_istack (Local_Stack);
  137.   return (Found);
  138.   }
  139.  
  140. int All_CSG_Merge_Intersections (Object, Ray, Depth_Stack)
  141. OBJECT *Object;
  142. RAY *Ray;
  143. ISTACK *Depth_Stack;
  144.   {
  145.   register int Found, inside_flag;
  146.   OBJECT *Sib1, *Sib2;
  147.   ISTACK *Local_Stack;
  148.   INTERSECTION *Sibling_Intersection;
  149.  
  150.   Found = FALSE;
  151.  
  152.   Local_Stack = open_istack ();
  153.  
  154.   for (Sib1 = ((CSG *)Object)->Children;
  155.        Sib1 != NULL ;
  156.        Sib1 = Sib1->Sibling)
  157.     if (Ray_In_Bounds (Ray, Sib1->Bound))
  158.       if (All_Intersections (Sib1, Ray, Local_Stack))
  159.         while ((Sibling_Intersection = pop_entry (Local_Stack)) !=  NULL)
  160.           if (Point_In_Clip (&Sibling_Intersection->IPoint,Object->Clip)) 
  161.           {
  162.           inside_flag = TRUE;
  163.           for (Sib2 = ((CSG *)Object)->Children;
  164.                Sib2 != NULL && inside_flag == TRUE;
  165.                Sib2 = Sib2->Sibling)
  166.             if (Sib1 != Sib2)
  167.               if (Inside_Object(&Sibling_Intersection->IPoint,Sib2))
  168.                 inside_flag = FALSE;
  169.           if (inside_flag == TRUE) 
  170.             {
  171.             Found = TRUE;
  172.             push_copy (Depth_Stack, Sibling_Intersection);
  173.             }
  174.           }
  175.   close_istack (Local_Stack);
  176.   return (Found);
  177.   }
  178.  
  179. int Inside_CSG_Union (IPoint, Object)
  180. VECTOR *IPoint;
  181. OBJECT *Object;
  182.   {
  183.   OBJECT *Current_Sib;
  184.  
  185.   for (Current_Sib = ((CSG *)Object)->Children;
  186.   Current_Sib != NULL ;
  187.   Current_Sib = Current_Sib->Sibling)
  188.     if (Inside_Object (IPoint, Current_Sib))
  189.       return (TRUE);
  190.  
  191.   return (FALSE);
  192.   }
  193.  
  194. int Inside_CSG_Intersection (IPoint, Object)
  195. OBJECT *Object;
  196. VECTOR *IPoint;
  197.   {
  198.   OBJECT *Current_Sib;
  199.  
  200.   for (Current_Sib = ((CSG *)Object)->Children;
  201.   Current_Sib != NULL ;
  202.   Current_Sib = Current_Sib->Sibling)
  203.     if (!Inside_Object (IPoint, Current_Sib))
  204.       return (FALSE);
  205.  
  206.   return (TRUE);
  207.   }
  208.  
  209. void *Copy_CSG (Object)
  210. OBJECT *Object;
  211.   {
  212.   CSG *New;
  213.   OBJECT *Old_Sib, *New_Sib, *Prev_Sib;
  214.  
  215.   if ((New = (CSG *) malloc (sizeof (CSG))) == NULL)
  216.     MAError ("CSG");
  217.  
  218.   New->Children = Prev_Sib = NULL;
  219.  
  220.   for (Old_Sib = ((CSG *)Object)->Children;
  221.   Old_Sib != NULL ;
  222.   Old_Sib = Old_Sib->Sibling) 
  223.     {
  224.     New_Sib = Copy_Object (Old_Sib);
  225.  
  226.     if (New->Children == NULL)
  227.       New->Children = New_Sib;
  228.  
  229.     if (Prev_Sib != NULL)
  230.       Prev_Sib->Sibling = New_Sib;
  231.  
  232.     Prev_Sib = New_Sib;
  233.     }
  234.  
  235.   return (New);
  236.   }
  237.  
  238. void Translate_CSG (Object, Vector)
  239. OBJECT *Object;
  240. VECTOR *Vector;
  241.   {
  242.   OBJECT *Sib;
  243.  
  244.   for (Sib = ((CSG *) Object)->Children;
  245.   Sib != NULL ;
  246.   Sib = Sib->Sibling)
  247.     Translate_Object (Sib, Vector);   
  248.   Compute_CSG_Bounds(Object);
  249.   }
  250.  
  251. void Rotate_CSG (Object, Vector)
  252. OBJECT *Object;
  253. VECTOR *Vector;
  254.   {
  255.   OBJECT *Sib;
  256.  
  257.   for (Sib = ((CSG *) Object)->Children;
  258.   Sib != NULL ;
  259.   Sib = Sib->Sibling)
  260.     Rotate_Object (Sib, Vector);   
  261.   Compute_CSG_Bounds(Object);
  262.   }
  263.  
  264. void Scale_CSG (Object, Vector)
  265. OBJECT *Object;
  266. VECTOR *Vector;
  267.   {
  268.   OBJECT *Sib;
  269.  
  270.   for (Sib = ((CSG *) Object)->Children;
  271.   Sib != NULL ;
  272.   Sib = Sib->Sibling)
  273.     Scale_Object (Sib, Vector);   
  274.   Compute_CSG_Bounds(Object);
  275.   }
  276.  
  277. void Transform_CSG (Object, Trans)
  278. OBJECT *Object;
  279. TRANSFORM *Trans;
  280.   {
  281.   OBJECT *Sib;
  282.  
  283.   for (Sib = ((CSG *) Object)->Children;
  284.   Sib != NULL ;
  285.   Sib = Sib->Sibling)
  286.     Transform_Object (Sib, Trans);   
  287.   Compute_CSG_Bounds(Object);
  288.   }
  289.  
  290. void Destroy_CSG (Object)
  291. OBJECT *Object;
  292.   {
  293.   Destroy_Object (((CSG *) Object)->Children);
  294.   free (Object);
  295.   }
  296.  
  297. void Invert_CSG_Union (Object)
  298. OBJECT *Object;
  299.   {
  300.   OBJECT *Sib;
  301.  
  302.   Object->Methods = &CSG_Intersection_Methods;
  303.  
  304.   for (Sib = ((CSG *)Object)->Children;
  305.   Sib != NULL ;
  306.   Sib = Sib->Sibling)
  307.     Invert_Object (Sib);
  308.   }
  309.  
  310. void Invert_CSG_Intersection (Object)
  311. OBJECT *Object;
  312.   {
  313.   OBJECT *Sib;
  314.  
  315.   Object->Methods = &CSG_Union_Methods;
  316.  
  317.   for (Sib = ((CSG *)Object)->Children;
  318.   Sib != NULL ;
  319.   Sib = Sib->Sibling)
  320.     Invert_Object (Sib);   
  321.   }
  322.  
  323. CSG *Create_CSG_Union ()
  324.   {
  325.   CSG *New;
  326.  
  327.   if ((New = (CSG *) malloc (sizeof (CSG))) == NULL)
  328.     MAError ("union");
  329.  
  330.   INIT_OBJECT_FIELDS(New, UNION_OBJECT, &CSG_Union_Methods)
  331.  
  332.     New->Children = NULL;
  333.   return (New);
  334.   }
  335.  
  336. CSG *Create_CSG_Merge ()
  337.   {
  338.   CSG *New;
  339.  
  340.   if ((New = (CSG *) malloc (sizeof (CSG))) == NULL)
  341.     MAError ("merge");
  342.  
  343.   INIT_OBJECT_FIELDS(New, MERGE_OBJECT, &CSG_Merge_Methods)
  344.  
  345.     New->Children = NULL;
  346.   return (New);
  347.   }
  348.  
  349. CSG *Create_CSG_Intersection ()
  350.   {
  351.   CSG *New;
  352.  
  353.   if ((New = (CSG *) malloc (sizeof (CSG))) == NULL)
  354.     MAError ("intersection");
  355.  
  356.   INIT_OBJECT_FIELDS(New, INTERSECTION_OBJECT, &CSG_Intersection_Methods)
  357.  
  358.     New->Children = NULL;
  359.   return (New);
  360.   }
  361.  
  362. void Compute_CSG_Bounds (Object)
  363. OBJECT *Object;
  364.   {
  365.   VECTOR mins, maxs;
  366.   DBL tmin, tmax;
  367.   OBJECT *Sib;
  368.  
  369.   Make_Vector(&mins,  BOUND_HUGE,  BOUND_HUGE,  BOUND_HUGE);
  370.   Make_Vector(&maxs, -BOUND_HUGE, -BOUND_HUGE, -BOUND_HUGE);
  371.  
  372.   for (Sib = ((CSG *) Object)->Children;
  373.   Sib != NULL ;
  374.   Sib = Sib->Sibling) 
  375.     {
  376.     tmin = Sib->Bounds.Lower_Left.x;
  377.     tmax = Sib->Bounds.Lower_Left.x + Sib->Bounds.Lengths.x;
  378.     if (tmin < mins.x) mins.x = tmin;
  379.     if (tmax > maxs.x) maxs.x = tmax;
  380.     tmin = Sib->Bounds.Lower_Left.y;
  381.     tmax = Sib->Bounds.Lower_Left.y + Sib->Bounds.Lengths.y;
  382.     if (tmin < mins.y) mins.y = tmin;
  383.     if (tmax > maxs.y) maxs.y = tmax;
  384.     tmin = Sib->Bounds.Lower_Left.z;
  385.     tmax = Sib->Bounds.Lower_Left.z + Sib->Bounds.Lengths.z;
  386.     if (tmin < mins.z) mins.z = tmin;
  387.     if (tmax > maxs.z) maxs.z = tmax;
  388.     }
  389.   Object->Bounds.Lower_Left = mins;
  390.   VSub(Object->Bounds.Lengths, maxs, mins);
  391.   }
  392.